扩欧理解ex | 您所在的位置:网站首页 › 证明ex>ex › 扩欧理解ex |
ex_gcd 一直以来都不是很懂扩欧是啥,只知道怎么用,现在来小小的写一波理解吧,毕竟完全靠记模板也是不行的。
首先扩欧是用来解决 ax+by=c 这种问题的。
然后 有这么一个定理 ax+by=gcd(a,b) 一定有解。 由欧几里得定理我们知道 gcd(a,b)=gcd(b,a%b)——>bx+(a%b)y=ax+by 下面就涉及到取模的本质了。
稍微想想就知道了。 带入: bx1+(a-a/b*b)y1=ax+by —>bx1+ay1-(a/b)*by1=ax+by —>ay1+b(x1-(a/b)*by1)=ax+by 我们发现 x=y1; y=(x1-(a/b)*y1) 这样我们就得到了一组解。那么ex_gcd 的c++模板就出来了。 int ex_gcd(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int d=ex_gcd(b,a%b,y,x); y-=(a/b)*x; return d; } void ex_gcd(int a,int b,int &d,int &x,int &y) { if(b==0) { x=1; y=0; d=a; } else { ex_gcd(b,a%b,d,y,x); y-=(a/b)*x; } }两种大概差不多吧,就有时候选择用会方便一点。
对于ax+by=c ;我们求出了ax+by=gcd(a,b) 那么原式的解就是: x=x'*(c/gcd(a,b)) y=y'*(c/gcd(a,b)) 我们可以看出,当 c%gcd(a,b)!=0 时,没有整数解。 这时候我们得出一组特解,那么我们如何找到通解呢: 其实这就相当于你在特解的基础上加上或减去某个数,和不变,我们需要找到最小的情况,即范围最大的情况. 那么就有: x=x1-b/gcd(a,b) *T (T为未知数) y=y1-a/(gcd(a,b) *T 这时我们就求出x,y 的通解了。
|
CopyRight 2018-2019 实验室设备网 版权所有 |